<!DOCTYPE HTML>
<html lang="zh-CN">
<head>
    

<head><meta name="generator" content="Hexo 3.8.0">
    <meta charset="utf-8">
    <meta name="keywords" content="剑指offer, 炫杉">
    <meta name="description" content="《剑指Offer》读书笔记。感谢强哥给的书。希望明年的我也可以Offer满满~
代码基本都在这里了：https://github.com/ixsim/OJ

Problems
 P25这个例子。先学好C++基础吧！
 P28 C#和C++不">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <title>剑指offer | 炫杉</title>
    <link rel="icon" type="image/png" href="/favicon.png">

    <link rel="stylesheet" type="text/css" href="/libs/awesome/css/font-awesome.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/materialize/css/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/css/my.css">

    <script src="/libs/jquery/jquery-2.2.0.min.js"></script>
<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css">
<link rel="stylesheet" href="/css/prism-line-numbers.css" type="text/css"></head>

</head>

<body>

<header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="container">
            <div class="nav-wrapper">
                <div class="brand-logo">
                    <a href="/" class="waves-effect waves-light">
                        
                        <img src="/medias/logo.png" class="logo-img hide-on-small-only">
                        
                        <span class="logo-span">炫杉</span>
                    </a>
                </div>
                <a href="#" data-activates="mobile-nav" class="button-collapse"><i class="fa fa-navicon"></i></a>
<ul class="right">
    
    <li class="hide-on-med-and-down">
        <a href="/" class="waves-effect waves-light">
            
            <i class="fa fa-home"></i>
            
            <span>Index</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/tags" class="waves-effect waves-light">
            
            <i class="fa fa-tags"></i>
            
            <span>Tags</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/categories" class="waves-effect waves-light">
            
            <i class="fa fa-bookmark"></i>
            
            <span>Categories</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/archives" class="waves-effect waves-light">
            
            <i class="fa fa-archive"></i>
            
            <span>Archives</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/about" class="waves-effect waves-light">
            
            <i class="fa fa-user-circle-o"></i>
            
            <span>About</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="https://oo1.win" class="waves-effect waves-light">
            
            <i class="fa fa-star"></i>
            
            <span>Bookmark</span>
        </a>
    </li>
    
    <li>
        <a id="toggleSearch" class="waves-effect waves-light">
            <i id="searchIcon" class="mdi-action-search"></i>
        </a>
    </li>

</ul>

<div class="side-nav" id="mobile-nav">

    <div class="mobile-head bg-color">
        
        <img src="/medias/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">炫杉</div>
        <div class="logo-desc">
            
            提着鸟笼的老头站在一旁拍我肩膀 我猜他想的应该和我一样
            
        </div>
    </div>

    <ul class="menu-list mobile-menu-list">
        
        <li>
            <a href="/" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-home"></i>
                
                Index
            </a>
        </li>
        
        <li>
            <a href="/tags" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-tags"></i>
                
                Tags
            </a>
        </li>
        
        <li>
            <a href="/categories" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-bookmark"></i>
                
                Categories
            </a>
        </li>
        
        <li>
            <a href="/archives" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-archive"></i>
                
                Archives
            </a>
        </li>
        
        <li>
            <a href="/about" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-user-circle-o"></i>
                
                About
            </a>
        </li>
        
        <li>
            <a href="https://oo1.win" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-star"></i>
                
                Bookmark
            </a>
        </li>
        
        
    </ul>

    <div class="social-link"><a href="https://github.com/ixsim" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
    <i class="fa fa-github"></i>
</a>

<a href="mailto:chenjiayin1990@163.com" class="tooltipped" target="_blank" data-tooltip="邮件:chinalixs@qq.com" data-position="top" data-delay="50">
    <i class="fa fa-envelope-open"></i>
</a>

<a href="http://wpa.qq.com/msgrd?v=3&uin=6956820&site=qq&menu=yes" class="tooltipped" data-tooltip="QQ: 6956820" data-position="top" data-delay="50">
    <i class="fa fa-qq"></i>
</a>
</div>
</div>

            </div>
        </div>

        
    </nav>
</header>



<div class="bg-cover post-cover" style="background-image: url('/medias/featureimages/14.jpg')">
    <div class="container">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <div class="description center-align post-title">
                        剑指offer
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>



<main class="post-container content">

    
    <link rel="stylesheet" href="/libs/tocbot/tocbot.css">
<style>
    #articleContent h1,
    #articleContent h2,
    #articleContent h3,
    #articleContent h4,
    #articleContent h5,
    #articleContent h6 {
        padding-top: 76px;
        margin-top: -76px;
    }

    #articleContent h1 {
        line-height: 3.5rem;
    }

    #articleContent h2 {
        line-height: 3.2rem;
    }

    #articleContent h3 {
        line-height: 2.8rem;
    }

    #articleContent h4 {
        line-height: 2.5rem;
    }

    #articleContent h5 {
        line-height: 2.2rem;
    }

    #articleContent h6 {
        line-height: 1.9rem;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        margin: 35px 0 15px 0;
        padding-left: 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #toc-content .is-active-link::before {
        background-color: #42b983;
    }
</style>
<div class="row">
    <div class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            
            <div class="article-tag">
                
                <a href="/tags/Note/" target="_blank">
                    <span class="chip bg-color">Note</span>
                </a>
                
            </div>
            
            <div class="post-info">
                
                <span class="post-cate">
                    <i class="fa fa-bookmark fa-fw icon-category"></i>
                    
                    <a href="/categories/Algorithm/" class="post-category" target="_blank">
                        Algorithm
                    </a>
                    
                </span>
                

                <span class="post-date">
                    <i class="fa fa-clock-o fa-fw"></i>2018-10-19
                </span>
            </div>
        </div>
        <hr>
        <div class="card-content article-card-content">
            <div id="articleContent">
                <p>《剑指Offer》读书笔记。感谢强哥给的书。希望明年的我也可以Offer满满~</p>
<p>代码基本都在这里了：<a href="https://github.com/ixsim/OJ" target="_blank" rel="noopener">https://github.com/ixsim/OJ</a></p>
<a id="more"></a>
<h1 id="Problems"><a href="#Problems" class="headerlink" title="Problems"></a>Problems</h1><ul>
<li style="list-style: none"><input type="checkbox"> P25这个例子。先学好C++基础吧！</li>
<li style="list-style: none"><input type="checkbox"> P28 C#和C++不一样那一段。在堆上分配内存和在栈上分配内存有什么不同。</li>
<li style="list-style: none"><input type="checkbox"> P31单例模式  研究不了 PASS </li>
<li style="list-style: none"><input type="checkbox"> 红黑树    据说和30题有关</li>
<li style="list-style: none"><input type="checkbox"> P75 斐波那契的公式法</li>
<li style="list-style: none"><input type="checkbox"> P82 位运算相关的题目和笔记是薄弱环节</li>
<li style="list-style: none"><input type="checkbox"> <a href="#11 数值的整数次方">11 数值的整数次方</a> 高效法重刷</li>
<li style="list-style: none"><input type="checkbox"> <a href="#12 打印1到n位最大数">12</a> 递归法重刷</li>
<li style="list-style: none"><input type="checkbox"> </li>
</ul>
<h1 id="Notes"><a href="#Notes" class="headerlink" title="Notes"></a>Notes</h1><ul>
<li>在C/C++中，数组作为函数的参数进行传递时，数组就自动退化为同类型的指针。</li>
<li>很多需要快速找到最大值或最小值的问题都可以用【堆】来解决</li>
<li>由于精度原因不能用等号判断两个小数是否相等。如果两个小数差的绝对值很小，就可以认为他们相等</li>
<li></li>
</ul>
<h1 id="第二章"><a href="#第二章" class="headerlink" title="第二章"></a>第二章</h1><h2 id="3搜索二维数组"><a href="#3搜索二维数组" class="headerlink" title="3搜索二维数组"></a>3搜索二维数组</h2><ul>
<li><p>牛客的没AC。先LeetCode上找了74搜索二维矩阵，这个稍微简单点，用一个二分查找就可以。然后240题搜索二维矩阵II就是一样的了。</p>
</li>
<li><p>看书知道了要删减的思路后。就从右上角开始。先排除的列，又排除的行。然后继续用<strong>最笨的方法去查找</strong>（其实也是一步步排除行和列的过程）。没有考虑到：</p>
<p>排除 列 和 行 的过程可以<strong>同时进行</strong>，直到循环结束啊。</p>
</li>
<li><p>PS:我之前这种思路是错误的：</p>
<p>类似二分查找，先找到要搜的列，再从这一列用二分查找。这样其实有的元素存在，但并不在你要找的这一列。</p>
</li>
</ul>
<h2 id="4替换空格"><a href="#4替换空格" class="headerlink" title="4替换空格"></a>4替换空格</h2><h2 id="5尾到头打印链表"><a href="#5尾到头打印链表" class="headerlink" title="5尾到头打印链表"></a>5尾到头打印链表</h2><p>用栈比较easy了.但是<strong>递归</strong>的写法注意：</p>
<pre class="line-numbers language-c++"><code class="language-c++">//我的写法：
while(node->next!=nullptr){function递归(a,b);}
//1.递归不能用while 要用if 啊
//2.不能只看是不是最后一个节点。还要看当前节点：
if(node!=null){
    if(node!=nullptr){
        func();
    }
}
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="6重建二叉树"><a href="#6重建二叉树" class="headerlink" title="6重建二叉树"></a>6重建二叉树</h2><p>确定递归思路后全靠自己一口气撸下来，⌘ + R , 测试没问题 。提交OJ。PASS。这一周看书最爽的一次AC。</p>
<h2 id="7用两个栈实现队列"><a href="#7用两个栈实现队列" class="headerlink" title="7用两个栈实现队列"></a>7用两个栈实现队列</h2><p>虽然自己写AC了。但是方案不如书上。</p>
<p>我是借助stack2进行pop, 每次pop完再回传给stack1。</p>
<p>其实不需要的。好好考虑考虑吧！</p>
<h2 id="8-旋转数组的min"><a href="#8-旋转数组的min" class="headerlink" title="8 旋转数组的min"></a>8 旋转数组的min</h2><p>看似水题。但遍历一次要O(N)</p>
<p>二分查找可以边O(logN)。然后还要考虑特殊情况。不可轻视</p>
<h2 id="9-斐波那契"><a href="#9-斐波那契" class="headerlink" title="9 斐波那契"></a>9 斐波那契</h2><p>除了普通法和递归法，要注意还有O(logN)的解法。</p>
<h2 id="10-二进制中1的个数"><a href="#10-二进制中1的个数" class="headerlink" title="10 二进制中1的个数"></a>10 二进制中1的个数</h2><p>位运算。</p>
<ul>
<li><p>1不停地执行左移。执行到首位（符号位）不就成了负的？然后再左移不就永远成了负的？</p>
<p>ANS: 左移不会保留符号位。右移才保留</p>
</li>
<li><p>位运算效率远高于乘除。尽可能得用位运算代替乘除。</p>
</li>
</ul>
<h1 id="第三章"><a href="#第三章" class="headerlink" title="第三章"></a>第三章</h1><h2 id="11-数值的整数次方"><a href="#11-数值的整数次方" class="headerlink" title="11 数值的整数次方"></a>11 数值的整数次方</h2><p>马马虎虎地过了，看了书后发现，我并没有考虑底数是特殊值的情况。（只分了指数的情况）</p>
<p>其实底数也有特殊情况。就是底数为0的时候，指数为负要抛出异常。</p>
<p>Note：</p>
<ul>
<li>用全局变量的方式抛出异常。</li>
<li>由于底数是double型，不能直接用==判断是否是0。要专门写一个函数来判断。</li>
</ul>
<p>然后就是高效的解法：</p>
<ul>
<li style="list-style: none"><input type="checkbox"> 这个解法一定要重刷！</li>
</ul>
<h2 id="12-打印1到n位最大数"><a href="#12-打印1到n位最大数" class="headerlink" title="12 打印1到n位最大数"></a>12 打印1到n位最大数</h2><p>不能用int型。要用string型。</p>
<ul>
<li style="list-style: none"><input type="checkbox"> 递归的写法要注意！</li>
</ul>
<h2 id="13-O-1-时间内删除链表节点"><a href="#13-O-1-时间内删除链表节点" class="headerlink" title="13 O(1)时间内删除链表节点"></a>13 O(1)时间内删除链表节点</h2><p>题目思路简单。注意这种情况：</p>
<ul>
<li><strong>只有一个节点，要删除这个节点。</strong></li>
</ul>
<h2 id="14-调整数组顺序"><a href="#14-调整数组顺序" class="headerlink" title="14 调整数组顺序"></a>14 调整数组顺序</h2><p>判断奇数偶数这回我知道用位运算了。但是请注意这个Warn：</p>
<ul>
<li><code>&amp; has lower precedence than ==;</code>  等号运算符的优先级高于&amp;！所以要用位运算判断的与或非 <strong>记得加括号</strong></li>
</ul>
<h2 id="15-链表中倒数第k个节点"><a href="#15-链表中倒数第k个节点" class="headerlink" title="15 链表中倒数第k个节点"></a>15 链表中倒数第k个节点</h2><ul>
<li><p>我这个二傻子。把节点一个个存到栈里。然后出栈到第k个。AC了。</p>
<p>为啥不存到vector里然后用下标就能返回倒数第k个呢。</p>
</li>
<li><p>书上的方法，用两个指针，两个相距k，当一个走到尾的时候，另个就是答案了。</p>
<ul>
<li style="list-style: none"><input type="checkbox"> 这个方法需要重刷。因为要考虑到鲁棒性问题。</li>
</ul>
</li>
</ul>
<h2 id="16-反转链表"><a href="#16-反转链表" class="headerlink" title="16 反转链表"></a>16 反转链表</h2><p>先用了栈做。龙哥刚好过来。让我自己想想别用栈。我一想。哈哈。挺简单。</p>
<h2 id="17-合并有序链表"><a href="#17-合并有序链表" class="headerlink" title="17 合并有序链表"></a>17 合并有序链表</h2><p>我用循环写的。比较简单。Note:</p>
<ul>
<li style="list-style: none"><input type="checkbox"> 用递归做一遍</li>
</ul>
<h2 id="18-判断是不是树的子结构"><a href="#18-判断是不是树的子结构" class="headerlink" title="18 判断是不是树的子结构"></a>18 判断是不是树的子结构</h2><p>我最后AC的版本存在本地了。有这么个错误代码需要注意：</p>
<pre class="line-numbers language-cpp"><code class="language-cpp"><span class="token keyword">bool</span> <span class="token function">HasSubtree</span><span class="token punctuation">(</span>TreeNode<span class="token operator">*</span> p1<span class="token punctuation">,</span> TreeNode<span class="token operator">*</span> p2<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>p1<span class="token operator">==</span><span class="token keyword">nullptr</span><span class="token operator">||</span>p2<span class="token operator">==</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span>
        <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>p1<span class="token operator">-</span><span class="token operator">></span>val<span class="token operator">==</span>p2<span class="token operator">-</span><span class="token operator">></span>val<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>   
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isSame</span><span class="token punctuation">(</span>p1<span class="token punctuation">,</span>p2<span class="token punctuation">)</span><span class="token punctuation">)</span>
            <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>p1<span class="token operator">-</span><span class="token operator">></span>left<span class="token punctuation">)</span>
                <span class="token function">HasSubtree</span><span class="token punctuation">(</span>p1<span class="token operator">-</span><span class="token operator">></span>left<span class="token punctuation">,</span>p2<span class="token punctuation">)</span><span class="token punctuation">;</span> 
            <span class="token keyword">if</span><span class="token punctuation">(</span>p1<span class="token operator">-</span><span class="token operator">></span>right<span class="token punctuation">)</span>
                <span class="token function">HasSubtree</span><span class="token punctuation">(</span>p1<span class="token operator">-</span><span class="token operator">></span>right<span class="token punctuation">,</span>p2<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>问题出现在第10行。我的想法是，如果有左子树就去走左子树。但是Debug的时候我发现，就算走到了第7行的return true, 程序也不会返回true的。因为我的第10行根本没有返回啊。只是去走一走。返回的一个true是从栈里返回到了第10行，并没有从第10行返回给main啊。</p>
<ul>
<li style="list-style: none"><input type="checkbox"> 重刷标记</li>
</ul>
<p>PS：这题牛客的测试用例绝对不全。</p>
<h3 id="amp-amp-的短路特性"><a href="#amp-amp-的短路特性" class="headerlink" title="&amp;&amp;的短路特性"></a>&amp;&amp;的短路特性</h3><pre class="line-numbers language-cpp"><code class="language-cpp"><span class="token comment" spellcheck="true">/*求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句.
解：利用&amp;&amp;的短路特性：如a&amp;&amp;b即如果a为假，b则被短路（不运算）
*/</span><span class="token keyword">int</span> <span class="token function">add_fun</span><span class="token punctuation">(</span>intn<span class="token punctuation">)</span>                  
<span class="token punctuation">{</span>   <span class="token keyword">int</span> num<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">(</span>n<span class="token operator">></span><span class="token number">0</span><span class="token punctuation">)</span><span class="token operator">&amp;&amp;</span><span class="token punctuation">(</span>num<span class="token operator">=</span>n<span class="token operator">+</span><span class="token function">add_fun</span><span class="token punctuation">(</span>n<span class="token number">-1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>     
    <span class="token keyword">return</span> num<span class="token punctuation">;</span>       
<span class="token punctuation">}</span> 
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span> <span class="token punctuation">)</span> 
<span class="token punctuation">{</span> 
    intsum<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> 
    intn<span class="token operator">=</span><span class="token number">100</span><span class="token punctuation">;</span>  
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span><span class="token function">add_fun</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
    return0<span class="token punctuation">;</span> 
<span class="token punctuation">}</span> 
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h1 id="第四章"><a href="#第四章" class="headerlink" title="第四章"></a>第四章</h1><h2 id="19-二叉树的镜像"><a href="#19-二叉树的镜像" class="headerlink" title="19 二叉树的镜像"></a>19 二叉树的镜像</h2><p>easy 秒过</p>
<h2 id="20-顺时针打印"><a href="#20-顺时针打印" class="headerlink" title="20 顺时针打印"></a>20 顺时针打印</h2><p>思路清晰。一次撸过。下次看看自己怎么写的就好啦。</p>
<p>不要二刷。</p>
<h2 id="21最小栈"><a href="#21最小栈" class="headerlink" title="21最小栈"></a>21最小栈</h2><p>easy不多说</p>
<h2 id="22入栈出栈次序"><a href="#22入栈出栈次序" class="headerlink" title="22入栈出栈次序"></a>22入栈出栈次序</h2><p>知道了用辅助栈的思路。比较好写。</p>
<p>不过，我没仔细看书上的代码。有空还是好好看一看。</p>
<h2 id="23二叉树层序遍历"><a href="#23二叉树层序遍历" class="headerlink" title="23二叉树层序遍历"></a>23二叉树层序遍历</h2><p>层序遍历就用队列嘛。easy。</p>
<h2 id="24判断是不是后序遍历序列"><a href="#24判断是不是后序遍历序列" class="headerlink" title="24判断是不是后序遍历序列"></a>24判断是不是后序遍历序列</h2><p>没思路。看书吧！</p>
<p>看书知道了思路。过了。其中输入数组为空的情况没考虑。细心点！</p>
<h2 id="25路径选择"><a href="#25路径选择" class="headerlink" title="25路径选择"></a>25路径选择</h2><p>应该是深度优先搜索。但我最近脑子不转，写递归的思路老是抽。</p>
<p>老是想，这个节点遍历完往回退的时候，怎么减到当前的节点。</p>
<p>其实在循环的最后一步把栈给POP一下就行了</p>
<h2 id="26复杂链表的复制"><a href="#26复杂链表的复制" class="headerlink" title="26复杂链表的复制"></a>26复杂链表的复制</h2><p>我的思路还是很清晰的。用一个map存。Key是原链表的地址，Value是新链表的地址。这样就有了一一对应关系。看代码：</p>
<pre class="line-numbers language-cpp"><code class="language-cpp">RandomListNode<span class="token operator">*</span> <span class="token function">Clone</span><span class="token punctuation">(</span>RandomListNode<span class="token operator">*</span> pHead<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    RandomListNode <span class="token operator">*</span>ans <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">RandomListNode</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    RandomListNode <span class="token operator">*</span>cur <span class="token operator">=</span> ans<span class="token punctuation">;</span>

    map<span class="token operator">&lt;</span>RandomListNode <span class="token operator">*</span><span class="token punctuation">,</span>RandomListNode <span class="token operator">*</span><span class="token operator">></span> map<span class="token punctuation">;</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>pHead<span class="token operator">!=</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>map<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>pHead<span class="token punctuation">)</span><span class="token operator">!=</span>map<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span><span class="token comment" spellcheck="true">//如果有就不new了</span>
            cur<span class="token operator">-</span><span class="token operator">></span>next <span class="token operator">=</span> map<span class="token punctuation">[</span>pHead<span class="token punctuation">]</span><span class="token punctuation">;</span>
            cur <span class="token operator">=</span> cur<span class="token operator">-</span><span class="token operator">></span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span><span class="token comment" spellcheck="true">//没有就new了 并存到map里</span>
            RandomListNode <span class="token operator">*</span>tmp <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">RandomListNode</span><span class="token punctuation">(</span>pHead<span class="token operator">-</span><span class="token operator">></span>label<span class="token punctuation">)</span><span class="token punctuation">;</span>
            map<span class="token punctuation">[</span>pHead<span class="token punctuation">]</span> <span class="token operator">=</span> tmp<span class="token punctuation">;</span>
            cur<span class="token operator">-</span><span class="token operator">></span>next <span class="token operator">=</span> tmp<span class="token punctuation">;</span>
            cur <span class="token operator">=</span> cur<span class="token operator">-</span><span class="token operator">></span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>pHead<span class="token operator">-</span><span class="token operator">></span>random<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token comment" spellcheck="true">//寻找 map 中有没有 pHead的random</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>map<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>pHead<span class="token operator">-</span><span class="token operator">></span>random<span class="token punctuation">)</span><span class="token operator">!=</span>map<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span><span class="token comment" spellcheck="true">//如果有就指向</span>
                cur<span class="token operator">-</span><span class="token operator">></span>random <span class="token operator">=</span> map<span class="token punctuation">[</span>pHead<span class="token operator">-</span><span class="token operator">></span>random<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span><span class="token comment" spellcheck="true">//没有就new了并存到map里</span>
                RandomListNode <span class="token operator">*</span>tmp <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">RandomListNode</span><span class="token punctuation">(</span>pHead<span class="token operator">-</span><span class="token operator">></span>random<span class="token operator">-</span><span class="token operator">></span>label<span class="token punctuation">)</span><span class="token punctuation">;</span>
                map<span class="token punctuation">[</span>pHead<span class="token operator">-</span><span class="token operator">></span>random<span class="token punctuation">]</span> <span class="token operator">=</span> tmp<span class="token punctuation">;</span>
                cur<span class="token operator">-</span><span class="token operator">></span>random <span class="token operator">=</span> tmp<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        pHead <span class="token operator">=</span> pHead<span class="token operator">-</span><span class="token operator">></span>next<span class="token punctuation">;</span>

    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> ans<span class="token operator">-</span><span class="token operator">></span>next<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<ul>
<li>注意第20行的<code>if(pHead-&gt;random)</code> 之前一直过不了正是由于有的节点没有random指针，为空时自然取不到label值。以后写的时候要思考全面。</li>
<li style="list-style: none"><input type="checkbox"> 用书上的好方法刷一次</li>
</ul>
<h2 id="27-二叉树与双向链表"><a href="#27-二叉树与双向链表" class="headerlink" title="27 二叉树与双向链表"></a>27 二叉树与双向链表</h2><p>先中序遍历，存到栈里。</p>
<p>然后再设置左右子树就很简单了。</p>
<p>思路好想，关键是输入为null的特殊情况我一直没处理。导致过不了。</p>

            </div>
            <hr>

            

            <link rel="stylesheet" type="text/css" href="/libs/share/css/share.min.css">

<div id="article-share">
    
    <div class="social-share" data-disabled="qzone" data-wechat-qrcode-helper="<p>微信里点“发现”->“扫一扫”二维码便可查看分享。</p>"></div>
    
</div>

<script src="/libs/share/js/social-share.min.js"></script>

            <div class="reprint">
                <p>
                    <span class="reprint-tip">转载请注明: </span>
                    <a href="https://xuanshan.gitee.io" class="b-link-green">炫杉</a>
                    <i class="fa fa-angle-right fa-lg fa-fw text-color"></i>
                    <a href="/Algorithm/剑指offer/" class="b-link-green">剑指offer</a>
                </p>
            </div>
        </div>
    </div>

    

    

    

    
    <div class="livere-card card" data-aos="fade-up">
    <!-- 来必力City版安装代码 -->
    <div id="lv-container" class="card-content" data-id="city" data-uid="MTAyMC8yOTg2My82NDI5">
        <script type="text/javascript">
            (function (d, s) {
                let j, e = d.getElementsByTagName(s)[0];
                if (typeof LivereTower === 'function') {
                    return;
                }

                j = d.createElement(s);
                j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
                j.async = true;

                e.parentNode.insertBefore(j, e);
            })(document, 'script');
        </script>
        <noscript>为正常使用来必力评论功能请激活JavaScript。</noscript>
    </div>
    <!-- City版安装代码已完成 -->
</div>
    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge left-badge text-color">上一篇</div>
            <div class="card">
                <a href="/WebRTC/APPRTC分析记录/">
                    <div class="card-image">
                        
                        
                        <img src="/medias/featureimages/7.jpg" class="responsive-img" alt="APPRTC分析记录">
                        
                        <span class="card-title">APPRTC分析记录</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary">  WebRTC iOS端官方Demo 看 APPRTC 源码的记录
  
AppRTCMobile根目录
ARDAppClient+Internal.h

ARDAppClient.h
ARDAppClient.m

ARDAppEngi</div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="fa fa-clock-o fa-fw icon-date"></i>2018-11-01
                        </span>
                        <span class="publish-author">
                            
                            <i class="fa fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/WebRTC/" class="post-category" target="_blank">
                                    WebRTC
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/Note/" target="_blank">
                        <span class="chip bg-color">Note</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">下一篇</div>
            <div class="card">
                <a href="/Others/PackageMananger/">
                    <div class="card-image">
                        
                        
                        <img src="/medias/featureimages/22.jpg" class="responsive-img" alt="PackageMananger相关">
                        
                        <span class="card-title">PackageMananger相关</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary">Homebrew,Ruby,CocoaPods,npm使用时遇到的的命令、更换源、出现的问题，简单记录

Homebrew概念
Mac的软件包管理工具，类似于linux的apt-get，能在mac中方便地安装软件或者卸载软件。

安装Hom</div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="fa fa-clock-o fa-fw icon-date"></i>2018-10-15
                            </span>
                        <span class="publish-author">
                            
                            <i class="fa fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/Others/" class="post-category" target="_blank">
                                    Others
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/Note/" target="_blank">
                        <span class="chip bg-color">Note</span>
                    </a>
                    
                    <a href="/tags/Homebrew/" target="_blank">
                        <span class="chip bg-color">Homebrew</span>
                    </a>
                    
                    <a href="/tags/Ruby/" target="_blank">
                        <span class="chip bg-color">Ruby</span>
                    </a>
                    
                    <a href="/tags/CocoaPods/" target="_blank">
                        <span class="chip bg-color">CocoaPods</span>
                    </a>
                    
                    <a href="/tags/npm/" target="_blank">
                        <span class="chip bg-color">npm</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>
</div>
    </div>
    <div class="col l3 hide-on-med-and-down">
        <div class="toc-widget">
            <div class="toc-title">目录</div>
            <div id="toc-content">

            </div>
        </div>
    </div>
</div>

<script src="/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingSelector: 'h1,h2, h3, h4'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h1,h2, h3, h4').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });
    });
</script>
    

</main>

<footer class="page-footer bg-color">
    <div class="container row center-align">
        <div class="col s12 m8 l8 copy-right">
            &copy;<a href="https://o--o.win" target="_blank">炫杉2018</a> 
            <a href="https://hexo.io/" target="_blank">Hexo</a> 强力驱动
              主题 <a href="https://github.com/blinkfox/hexo-theme-matery" target="_blank">matery</a>        </div>
        <div class="col s12 m4 l4 social-link"><a href="https://github.com/ixsim" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
    <i class="fa fa-github"></i>
</a>

<a href="mailto:chenjiayin1990@163.com" class="tooltipped" target="_blank" data-tooltip="邮件:chinalixs@qq.com" data-position="top" data-delay="50">
    <i class="fa fa-envelope-open"></i>
</a>

<a href="http://wpa.qq.com/msgrd?v=3&uin=6956820&site=qq&menu=yes" class="tooltipped" data-tooltip="QQ: 6956820" data-position="top" data-delay="50">
    <i class="fa fa-qq"></i>
</a>
</div>
    </div>
</footer>

<div class="progress-bar"></div>


<!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title">搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字" class="search-input" autofocus>
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script src="/js/search.js"></script>
<script type="text/javascript">
    searchFunc("/" + "search.xml", 'searchInput', 'searchResult');
</script>
<!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fa fa-angle-up"></i>
    </a>
</div>


<script src="/libs/materialize/js/materialize.min.js"></script>
<script src="/libs/masonry/masonry.pkgd.min.js"></script>
<script src="/libs/aos/aos.js"></script>
<script src="/libs/scrollprogress/scrollProgress.min.js"></script>
<script src="/libs/lightGallery/js/lightgallery-all.min.js"></script>
<script src="/js/matery.js"></script>
</body>
</html>